#include <iostream>

using namespace std;

// 67. 二进制求和
// 给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
// 输入：a = "1010", b = "1011"
// 输出："10101"
class Solution {
public:
    string addBinary(string a, string b) {
        string res;
        int carry = 0;  // 进位
        int i = a.size() - 1;  // 从后往前运算
        int j = b.size() - 1;  // 这里不能用auto i或者auto j，也不能用size_t，因为size()返回的为unsigned long long，是无符号的，-1之后变成了非常大的负整数。
        while(i >= 0 || j >= 0 || carry != 0) {
            int A = i >= 0 ? a[i--] - '0' : 0;  // a字符串的当前位
            int B = j >= 0 ? b[j--] - '0' : 0;  // b字符串的当前位
            int sum = A + B + carry;    // 和值
            carry = sum / 2;    // 商进位
            res = to_string(sum % 2).append(res);  // 余数转字符串，加上已计算结果
        }
        return res;
    }
};
int main() {
    std::cout << Solution().addBinary("11", "1") << std::endl; // "100"
    std::cout << Solution().addBinary("1010", "1011") << std::endl; // "10101"
    std::cout << Solution().addBinary("1", "111") << std::endl; // "1000"
    std::cout << Solution().addBinary("100", "110010") << std::endl; // "1000"

    return 0;
}
